#ifndef SKEWHEAP_H
#define SKEWHEAP_H

#include <iomanip>
#include <iostream>
using namespace std;

template<class T>
class SkewNode
{
public:
    T key;
    SkewNode *left;        // 左孩子
    SkewNode *right;    // 右孩子

    SkewNode(T value, SkewNode *l, SkewNode *r):
        key(value), left(l),right(r) {}
};

template<class T>
class SkewHeap
{private:
    SkewNode<T> *mRoot;    // 根结点

public:
    SkewHeap();
    ~SkewHeap();

    // 前序遍历"斜堆"
    void preOrder();
    // 中序遍历"斜堆"
    void inOrder();
    // 后序遍历"斜堆"
    void postOrder();

     // 将other的斜堆合并到this中。
    void merge(SkewHeap<T>* other);
    // 将结点(key为节点键值)插入到斜堆中
    void insert(T key);
    // 删除结点(key为节点键值)
    void remove();

    // 销毁斜堆
    void destroy();

    // 打印斜堆
    void print();
private:

    // 前序遍历"斜堆"
    void preOrder(SkewNode<T>* heap) const;
    // 中序遍历"斜堆"
    void inOrder(SkewNode<T>* heap) const;
    // 后序遍历"斜堆"
    void postOrder(SkewNode<T>* heap) const;

    // 交换节点x和节点y
    void swapNode(SkewNode<T> *&x, SkewNode<T> *&y);
    // 合并"斜堆x"和"斜堆y"
    SkewNode<T>* merge(SkewNode<T>* &x, SkewNode<T>* &y);

    // 销毁斜堆
    void destroy(SkewNode<T>* &heap);

    // 打印斜堆
    void print(SkewNode<T>* heap, T key, int direction);
};


template<class T>
SkewHeap<T>::SkewHeap():mRoot(nullptr)
{
}

template<class T>
SkewHeap<T>::~SkewHeap()
{
    destroy(mRoot);
}

template<class T>
void SkewHeap<T>::preOrder(SkewNode<T> *heap) const
{
    if(heap != nullptr)
    {
        cout << heap->key << " ";
        preOrder(heap->left);
        preOrder(heap->right);
    }
}

template<class T>
void SkewHeap<T>::preOrder()
{
   preOrder(mRoot);
}

template<class T>
void SkewHeap<T>::inOrder(SkewNode<T> *heap) const
{
    if(heap != nullptr)
    {
        inOrder(heap->left);
        cout << heap->key << " ";
        inOrder(heap->right);
    }
}

template<class T>
void SkewHeap<T>::inOrder()
{
   inOrder(mRoot);
}

template<class T>
void SkewHeap<T>::postOrder(SkewNode<T> *heap) const
{
    if(heap != nullptr)
    {
        postOrder(heap->left);
        postOrder(heap->right);
        cout << heap->key << " ";
    }
}

template<class T>
void SkewHeap<T>::postOrder()
{
   postOrder(mRoot);
}

template<class T>
void SkewHeap<T>::swapNode(SkewNode<T> *&x, SkewNode<T> *&y)
{
    auto tmp = x;
    x = y;
    y = tmp;
}

template<class T>
SkewNode<T> *SkewHeap<T>::merge(SkewNode<T> *&x, SkewNode<T> *&y)
{
    if(x == nullptr)
        return y;
    if( y == nullptr )
        return x;

    if(x->key > y->key)
        swapNode(x, y);

    auto tmp = merge(x->right, y);
    x->right = x->left;
    x->left = tmp;

    return x;
}

template<class T>
void SkewHeap<T>::merge(SkewHeap<T> *other)
{
    mRoot = merge(mRoot, other->mRoot);
}

template<class T>
void SkewHeap<T>::insert(T key)
{
    SkewNode<T> *node;

    node = new SkewNode<T>(key, nullptr, nullptr);
    if(node == nullptr)
    {
        cout << "ERROR: create node failed!" << endl;
        return ;
    }

    mRoot = merge(mRoot, node);
}

template<class T>
void SkewHeap<T>::remove()
{
    if(mRoot = nullptr)
        return nullptr;

    auto l = mRoot->left;
    auto r = mRoot->right;

    delete mRoot;
    mRoot = merge(l, r);
}


template<class T>
void SkewHeap<T>::destroy(SkewNode<T> *&heap)
{
    if(heap == nullptr)
        return ;

    if(heap->left != nullptr)
        destroy(heap->left);
    if(heap->right != nullptr)
        destroy(heap->right);

    delete heap;
}


template<class T>
void SkewHeap<T>::destroy()
{
    destroy(mRoot);
}

template <class T>
void SkewHeap<T>::print(SkewNode<T>* heap, T key, int direction)
{
    if(heap != NULL)
    {
        if(direction==0)    // heap是根节点
            cout << setw(2) << heap->key << " is root" << endl;
        else                // heap是分支节点
            cout << setw(2) << heap->key << " is " << setw(2) << key << "'s "  << setw(12) << (direction==1?"right child" : "left child") << endl;

        print(heap->left, heap->key, -1);
        print(heap->right,heap->key,  1);
    }
}

template <class T>
void SkewHeap<T>::print()
{
    if (mRoot != NULL)
        print(mRoot, mRoot->key, 0);
}


#endif // SKEWHEAP_H
